#include <string>
#include <fstream>
#include <vector>
#include <iostream>
#define NUM_VERTICES 5375

using namespace std;
vector<vector<int > > map(NUM_VERTICES);
vector<vector<int > > triangles;
void tokenize(const string& str,
                      vector<string>& tokens,
                      const string& delimiters = " ")
{   
    // Skip delimiters at beginning.
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);
    // Find first "non-delimiter".
    string::size_type pos     = str.find_first_of(delimiters, lastPos);

    while (string::npos != pos || string::npos != lastPos)
    { 
        // Found a token, add it to the vector.
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters.  Note the "not_of"
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next "non-delimiter"
        pos = str.find_first_of(delimiters, lastPos); 
    }
}   

void parseLine(string line)
{
    vector<string>tokens;
    tokenize(line, tokens);
    if (tokens.size() == 3)
    {
        //edges 4444 5555
        int v1 = atoi(tokens[1].c_str());
        int v2 = atoi(tokens[2].c_str());
        map[v1].push_back(v2);
        //map[v2].push_back(v1); 
    }
    else
        cout<<"Skipping "<<line<<endl;
}

/*
 * 1. read file. construct a map of vertices to all vertices connected to it.
 * 2. then, for every vertex, look up the other vertex and see 
*/

void readAndConstruct()
{
    ifstream stream;
    string line;
    char * mVFile = "ym.edges";
    stream.open(mVFile);
        if (!stream.is_open())
    {
        fprintf(stderr,"Failed to open %s\n", mVFile);
        exit(1);
    }
    while (! stream.eof())
    {
        getline(stream,line);
        parseLine(line);
    }

}

void printArray(vector<int> array)
{
    printf("printing array\n");
    for (int a = 0; a < array.size(); a++)
    {
        printf("%d ", array[a]); 
    }
    printf("\n");
}

void findThird(int one, int two)
{
    //printf("one : %d, two: %d\n", one, two);
    vector<int> array1, array2;
    array1 = map[one];
    array2 = map[two];
    //printArray(array1);
    //printArray(array2);
    for (int a = 0; a < array1.size(); a++)
    {
        for (int b = 0; b < array2.size(); b++)
        {
            //printf("a : %d, b: %d\n", a,b);
            if (array1[a] == array2[b])
            {
                //printf("found triangle: %d %d %d\n", one,two, array1[a]);
                vector<int> triangle(3);
                triangle[0] = one;
                triangle[1] = two;
                triangle[2] = array1[a];
                triangles.push_back(triangle);
            }
        }
    }
    //printf("findThird Done\n");
}

void findTriangles()
{
    vector<int> varray;
    for (int a = 0; a < map.size(); a++)
    {
        varray = map[a];
        for (int b = 0; b < varray.size(); b++)
        {
            findThird(a, varray[b]);
        }
    }
}

void writeFile()
{
        ofstream stream("found.txt");
    if (!stream){
        printf("Can't open file.\n");
        exit(2);
    }
    for (int a = 0; a < triangles.size(); a++)
    {
        vector<int> tri = triangles[a];
        stream << tri[0] << "\t" << tri[1] << "\t" << tri[2] <<endl;
    }
    stream.close();

}

int main()
{
    //edge 
    readAndConstruct();
    cout <<"Finding triangles"<<endl;
    findTriangles();
    writeFile();
    return 0;
}
